
//1471.数组中的k个最强值
class Solution {
public:
    vector<int> getStrongest(vector<int>& arr, int k) {
        int n=arr.size();
        sort(arr.begin(),arr.end());   //先进行排序找中间值
        int m=arr[(n-1)/2];

        //左右两边一定比中间强，所以控制[left,right]区间，从左右两边找最强值
        vector<int> ret;
        int left=0,right=n-1;
        while(k&&left<=right)
        {
            int lnum=abs(arr[left]-m);
            int rnum=abs(arr[right]-m);
            if(lnum>rnum)   //左边大，入左边
            {
                ret.push_back(arr[left]);
                left++;
            }
            else   //右边大，入右边
            {
                ret.push_back(arr[right]);
                right--;
            }
            k--;
        }

        return ret;
    }
};